package com.datastructure2.backtrack;

import org.junit.Test;

import java.lang.annotation.Target;
import java.sql.Array;
import java.util.*;

/**
 * @author: 临晖
 * @date: 2024/02/22
 * @description:
 */
public class Solution {


    /**
     * 77. 组合
     * 中等
     * 相关标签
     * 相关企业
     * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
     * 你可以按 任何顺序 返回答案。
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();

        com(1, n, k, res, path);

        return res;
    }

    public void com(int x, int n, int k, List<List<Integer>> res, List<Integer> path) {
        if (path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = x; i <= n; i++) {
            path.add(i);
            //递归
            com(i + 1, n, k, res, path);
            //回溯
            path.remove(path.size() - 1);
        }
    }


    /**
     * 216. 组合总和 III
     * 中等
     * 相关标签
     * 相关企业
     * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
     * 只使用数字1到9
     * 每个数字 最多使用一次
     * 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
     *
     * @param k
     * @param n
     * @return
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        ArrayList<Integer> path = new ArrayList<>();

        combinationSum3_(k, n, 1, res, path);
        return res;

    }

    public void combinationSum3_(int k, int n, int startX, List<List<Integer>> res, List<Integer> path) {
        if (path.size() == k) {
            int sum = 0;
            for (int x : path) {
                sum += x;
            }

            if (sum == n) {
                res.add(new ArrayList<>(path));
            }

            return;
        }

        for (int i = startX; i <= 9; i++) {
            path.add(i);

            combinationSum3_(k, n, i + 1, res, path);

            path.remove(path.size() - 1);
        }
    }


    /**
     * 17. 电话号码的字母组合
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
     *
     * @param digits
     * @return
     */
    String[] strs = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.equals("")) {
            return res;
        }

        letter("", digits, 0);
        return res;
    }

    /**
     * @param str    字母组合
     * @param digits
     * @param x      输入”233“， x表示轮到第几个数字了
     */
    public void letter(String str, String digits, int x) {
        if (x >= digits.length()) {
            res.add(str);
            return;
        }

        //按键数字
        int a = digits.charAt(x) - '0';
        for (int i = 0; i < strs[a].length(); i++) {
            str += strs[a].charAt(i);
            letter(str, digits, x + 1);
            //回溯
            str = str.substring(0, str.length() - 1);
        }
    }


    /**
     * 39. 组合总和
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     * 对于给定的输入，保证和为 target 的不同组合数少于 150 个
     *
     * @param candidates
     * @param target
     * @return
     */

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);        //排序
        combinatiionSum_(candidates, target, res, path, 0, 0);
        return res;

    }

    public void combinatiionSum_(int[] candidates, int target, List<List<Integer>> res, List<Integer> path, int sum, int x) {
        if (sum == target && path.size() != 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = x; i < candidates.length; i++) {
            //if (candidates[i] > target) {
            //    return;
            //}

            sum += candidates[i];
            if (sum > target) {
                return;
            }

            path.add(candidates[i]);


            combinatiionSum_(candidates, target, res, path, sum, i);

            path.remove(path.size() - 1);
            sum -= candidates[i];
        }
    }

    /**
     * 40. 组合总和 II
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的每个数字在每个组合中只能使用 一次 。
     * 注意：解集不能包含重复的组合。
     *
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);        //排序
        combinationSum2_(candidates, target, res, path, 0, 0);
        return res;
    }

    public void combinationSum2_(int[] candidates, int target, List<List<Integer>> res, List<Integer> path, int sum, int x) {
        if (sum == target && path.size() != 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = x; i < candidates.length; i++) {

            if (i > x && candidates[i] == candidates[i - 1]) {
                continue;
            }

            sum += candidates[i];

            if (sum > target) {
                return;
            }

            path.add(candidates[i]);
            combinationSum2_(candidates, target, res, path, sum, i + 1);

            sum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }


    /**
     * 131. 分割回文串
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
     * 回文串 是正着读和反着读都一样的字符串。
     *
     * @param s
     * @return
     */
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        partition_(s, 0, res, path);
        return res;
    }


    public void partition_(String s, int left, List<List<String>> res, List<String> path) {

        if (left >= s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }


        for (int i = left; i <= s.length() - 1; i++) {


            if (isPalindrome(s, left, i)) {      //是回文字串
                String str = s.substring(left, i + 1);
                path.add(str);
            } else {
                continue;
            }

            partition_(s, i + 1, res, path);
            path.remove(path.size() - 1);


        }
    }


    /**
     * 判断回文
     *
     * @param s
     * @return
     */
    public boolean isPalindrome(String s, int startIndex, int end) {


        while (startIndex <= end) {

            if (s.charAt(startIndex) != s.charAt(end)) {
                return false;
            }

            startIndex++;
            end--;
        }

        return true;
    }


    /**
     * 93. 复原 IP 地址
     * 中等
     * 相关标签
     * 相关企业
     * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
     *
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {
        ArrayList<String> res = new ArrayList<>();
        restoreIpAddresses_(s, res, 0, 0);
        return res;
    }

    public void restoreIpAddresses_(String s, List<String> res, int startIndex, int pointNum) {
        if (pointNum == 3) {
            if (isValid(s, startIndex, s.length() - 1)) {
                res.add(s);
            }
            return;

        }


        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {        //判断当前选取数字是否符合ip
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                pointNum++;

                //递归
                restoreIpAddresses_(s, res, i + 2, pointNum);

                //回溯
                pointNum--;
                int lastPointIndex = s.lastIndexOf('.');
                s = s.substring(0, lastPointIndex) + s.substring(lastPointIndex + 1);
            } else {
                break;
            }
        }


    }


    /**
     * 判断ip某段是否合法
     *
     * @param s
     * @param start
     * @param end
     * @return
     */
    boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到非数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果大于255了不合法
                return false;
            }
        }
        return true;
    }


    /**
     * 78. 子集
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。v
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        res.add(new ArrayList<>());

        if (nums.length == 0) {
            return res;
        }

        //递归
        subsets_(nums, res, path, 0);
        return res;
    }

    public void subsets_(int[] nums, List<List<Integer>> res, List<Integer> path, int startIndex) {
        //if (startIndex == nums.length) {
        //    res.add(new ArrayList<>(path));
        //    return;
        //}


        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            res.add(new ArrayList<>(path));


            //递归
            subsets_(nums, res, path, i + 1);

            path.remove(path.size() - 1);
        }
    }


    /**
     * 90. 子集 II
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        res.add(new ArrayList<>());

        if (nums.length == 0) {
            return res;
        }

        Arrays.sort(nums);
        //递归
        subsetsWithDup_(nums, res, path, 0);
        return res;
    }

    public void subsetsWithDup_(int[] nums, List<List<Integer>> res, List<Integer> path, int startIndex) {


        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }

            path.add(nums[i]);
            res.add(new ArrayList<>(path));

            //递归
            subsetsWithDup_(nums, res, path, i + 1);

            //回溯
            path.remove(path.size() - 1);
        }
    }


    /**
     * 491. 非递减子序列
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
     * 数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();


        if (nums.length == 0) {
            return res;
        }


        //递归
        finSubsequences_(nums, res, path, 0);

        return res;
    }

    public void finSubsequences_(int[] nums, List<List<Integer>> res, List<Integer> path, int startIndex) {

        if (path.size() >= 2) {
            res.add(new ArrayList<>(path));
        }

        HashMap<Integer, Boolean> map = new HashMap<>();        //使用过true，反之false

        //同一树枝可以重复，但是同一数层不可以重复
        for (int i = startIndex; i < nums.length; i++) {
            if (map.getOrDefault(nums[i], false)) {
                continue;
            }

            if (path.size() == 0 || path.get(path.size() - 1) <= nums[i]) {
                map.put(nums[i], true);     //标记，在当前层使用过该数字
                path.add(nums[i]);

                //递归
                finSubsequences_(nums, res, path, i + 1);

                path.remove(path.size() - 1);
            }

        }
    }


    /**
     * 46. 全排列
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();


        if (nums.length == 0) {
            return res;
        }

        boolean[] use = new boolean[nums.length];
        //递归
        permute_(nums, res, path, use);

        return res;
    }

    public void permute_(int[] nums, List<List<Integer>> res, List<Integer> path, boolean[] use) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {

            if (!use[i]) {
                path.add(nums[i]);
                use[i] = true;

                //递归
                permute_(nums, res, path, use);

                path.remove(path.size() - 1);
                use[i] = false;
            }

        }
    }


    /**
     * 47. 全排列 II
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();


        if (nums.length == 0) {
            return res;
        }

        boolean[] use = new boolean[nums.length];
        //递归
        Arrays.sort(nums);
        permuteUnique_(nums, res, path, use);

        return res;
    }


    public void permuteUnique_(int[] nums, List<List<Integer>> res, List<Integer> path, boolean[] use) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            //如果当前上一个元素为使用过，且当前元素等于上一个元素，那么吃鸡continue
            if (i > 0 && !use[i - 1] && nums[i] == nums[i - 1]) {
                continue;
            }

            if (!use[i]) {              //!use[i]:表示未使用         &&
                path.add(nums[i]);
                use[i] = true;

                //递归
                permuteUnique_(nums, res, path, use);

                path.remove(path.size() - 1);
                use[i] = false;
            }

        }
    }


    /**
     * 332. 重新安排行程
     * 困难
     * 相关标签
     * 相关企业
     * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
     * <p>
     * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
     * <p>
     * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
     * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次
     *
     * @param tickets
     * @return
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        LinkedList<String> res = new LinkedList<>();
        Map<String, Map<String, Integer>> map = new HashMap<>();


        for (List<String> t : tickets) {
            Map<String, Integer> temp;
            if (map.containsKey(t.get(0))) {
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();//升序Map
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);

        }


        res.add("JFK");
        findItinerary_(map, res, tickets.size() + 1);
        return res;
    }


    public boolean findItinerary_(Map<String, Map<String, Integer>> map, LinkedList<String> res, int ticketNum) {
        if (res.size() == ticketNum) {
            return true;
        }

        String last = res.getLast();
        if (map.containsKey(last)) {//防止出现null
            for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {
                int count = target.getValue();
                if (count > 0) {
                    res.add(target.getKey());
                    target.setValue(count - 1);
                    if (findItinerary_(map, res, ticketNum)) {
                        return true;
                    }

                    res.removeLast();
                    target.setValue(count);
                }
            }
        }

        return false;

    }


    /**
     * 51. N 皇后
     * 困难
     * 相关标签
     * 相关企业
     * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     *
     * @param n
     * @return
     */
    public List<List<String>> solveNQueens(int n) {
        int[] queens = new int[n];
        List<List<String>> res = new ArrayList<>();
        sloveNQueens(n, res, queens, 0);
        return res;
    }


    /**
     * @param n      表示n皇后
     * @param res    返回结果集
     * @param queens n皇后站位
     * @param toLine 到了第几行
     */
    public void sloveNQueens(int n, List<List<String>> res, int[] queens, int toLine) {
        if (toLine >= n) {
            List<String> path = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                int inQ = queens[i];
                String str = "";
                for (int j = 0; j < n; j++) {
                    if (inQ == j) {
                        str += "Q";
                    } else {
                        str += ".";
                    }
                }
                path.add(str);
            }
            res.add(path);

            return;
        }


        for (int i = 0; i < n; i++) {           //代表列
            //判断是否在一条线上
            if (!isInLine(queens, toLine, i)) {      //true可以
                continue;
            }

            queens[toLine] = i;

            //递归
            sloveNQueens(n, res, queens, toLine + 1);

            //回溯，
        }


    }


    public boolean isInLine(int[] queens, int x, int y) {
        for (int i = 0; i < x; i++) {       //表示行
            if (queens[i] == y) {       //是否在同一列
                return false;
            }

            if (Math.abs(x - i) == Math.abs(y - queens[i])) {       //表示在同一斜线
                return false;
            }

        }

        return true;
    }


    /**
     * 37. 解数独
     * 困难
     * 相关标签
     * 相关企业
     * 编写一个程序，通过填充空格来解决数独问题。
     * 数独的解法需 遵循如下规则：
     * 数字 1-9 在每一行只能出现一次。
     * 数字 1-9 在每一列只能出现一次。
     * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
     * 数独部分空格内已填入了数字，空白格用 '.' 表示。
     *
     * @param board
     */
    public void solveSudoku(char[][] board) {
        solveSudoku_(board, 0, 0);
    }

    public boolean solveSudoku_(char[][] board, int startX, int startY) {
        if (startX == board.length && startY == board[0].length) {
            return true;
        }


        if (startY == board[0].length) {
            startX += 1;
            startY = 0;

            if (startX == board.length) {
                return true;
            }
        }
        //如果当前是数字
        if (board[startX][startY] != '.') {
            //下一个

            return solveSudoku_(board, startX, startY + 1);
        }

        //不是数字
        for (char num = '1'; num <= '9'; num++) {
            board[startX][startY] = num;

            if (!isLegal(board, startX, startY)) {
                continue;
            }
            //递归
            if (solveSudoku_(board, startX, startY + 1)) {
                return true;
            }

        }
        board[startX][startY] = '.';

        return false;


    }


    /**
     * 判断是否在同一 3 * 3的九宫格
     * 判断是否在同一列
     * 判断是否在同一行
     *
     * @param board
     * @param x
     * @param y
     * @return
     */
    public boolean isLegal(char[][] board, int x, int y) {
        int xRemainder = x % 3;
        int yRemainder = y % 3;

        //计算出当前数字所在的 3 * 3范围
        int leftX = x - xRemainder;
        int rightX = leftX + 2;

        int heightY = y - yRemainder;
        int lowY = heightY + 2;

        for (int i = leftX; i <= rightX; i++) {
            for (int j = heightY; j <= lowY; j++) {
                if (board[i][j] == '.') {
                    continue;
                }

                if (i != x && j != y && board[i][j] == board[x][y]) {       //如果碰到相等的数字
                    return false;
                }
            }
        }

        //判断同一列是否有相同的
        for (int i = 0; i < board.length; i++) {
            if (i != x && board[i][y] == board[x][y]) {
                return false;
            }
        }

        for (int i = 0; i < board[0].length; i++) {
            if (i != y && board[x][i] == board[x][y]) {
                return false;
            }
        }

        return true;
    }


    @Test
    public void myTest() {
        char[][] board =
                {
                        {'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {
                        '6', '.', '.', '1', '9', '5', '.', '.', '.'}, {
                        '.', '9', '8', '.', '.', '.', '.', '6', '.'}, {
                        '8', '.', '.', '.', '6', '.', '.', '.', '3'}, {
                        '4', '.', '.', '8', '.', '3', '.', '.', '1'}, {
                        '7', '.', '.', '.', '2', '.', '.', '.', '6'}, {
                        '.', '6', '.', '.', '.', '.', '2', '8', '.'}, {
                        '.', '.', '.', '4', '1', '9', '.', '.', '5'}, {
                        '.', '.', '.', '.', '8', '.', '.', '7', '9'}
                };
        solveSudoku(board);

        for (char[] a : board) {
            for (char b : a) {
                System.out.print(b + " ");
            }
            System.out.println();
        }
    }



//for (int i = startX; i < board.length; i++) {
//    for (int j = startY; j < startY; j++) {
//        if (board[i][j] != '.') {
//            continue;
//        }
//
//        //等于'.'
//        for (char num = '0'; num <= '9'; num++) {
//            board[i][j] = num;
//            if (!isLegal(board, i, j)) {
//                continue;
//            }
//            //递归
//            if (solveSudoku_(board, i + 1, j + 1)) {
//                return true;
//            }
//
//        }
//
//        return false;
//    }
//}
//
//return false;
}
